{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Jump Game III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canReach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #跳跃游戏 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>这里有一个非负整数数组&nbsp;<code>arr</code>，你最开始位于该数组的起始下标&nbsp;<code>start</code>&nbsp;处。当你位于下标&nbsp;<code>i</code>&nbsp;处时，你可以跳到&nbsp;<code>i + arr[i]</code> 或者 <code>i - arr[i]</code>。</p>\n",
    "\n",
    "<p>请你判断自己是否能够跳到对应元素值为 0 的 <strong>任一</strong> 下标处。</p>\n",
    "\n",
    "<p>注意，不管是什么情况下，你都无法跳到数组之外。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [4,2,3,0,3,1,2], start = 5\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "到达值为 0 的下标 3 有以下可能方案： \n",
    "下标 5 -&gt; 下标 4 -&gt; 下标 1 -&gt; 下标 3 \n",
    "下标 5 -&gt; 下标 6 -&gt; 下标 4 -&gt; 下标 1 -&gt; 下标 3 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [4,2,3,0,3,1,2], start = 0\n",
    "<strong>输出：</strong>true \n",
    "<strong>解释：\n",
    "</strong>到达值为 0 的下标 3 有以下可能方案： \n",
    "下标 0 -&gt; 下标 4 -&gt; 下标 1 -&gt; 下标 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [3,0,2,1,2], start = 2\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>无法到达值为 0 的下标 1 处。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 5 * 10^4</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;&nbsp;arr.length</code></li>\n",
    "\t<li><code>0 &lt;= start &lt; arr.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jump-game-iii](https://leetcode.cn/problems/jump-game-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jump-game-iii](https://leetcode.cn/problems/jump-game-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,3,0,3,1,2]\\n5', '[4,2,3,0,3,1,2]\\n0', '[3,0,2,1,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        que = [start]\n",
    "\n",
    "        while que:\n",
    "            node = que.pop(0)\n",
    "            if arr[node] == 0:\n",
    "                return True\n",
    "            if arr[node] < 0:\n",
    "                continue\n",
    "            for i in [node + arr[node], node - arr[node]]:\n",
    "                if 0 <= i < n:\n",
    "                    que.append(i)\n",
    "                \n",
    "            arr[node] = -arr[node]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        d = dict()\n",
    "        def reach(arr, start):\n",
    "            if start >= len(arr) or start < 0 or d.get(start, None):\n",
    "                return False\n",
    "            if arr[start] == 0:\n",
    "                return True\n",
    "            d[start] = 1\n",
    "            res_left = reach(arr, start-arr[start])\n",
    "            res_right = reach(arr, start+arr[start])\n",
    "            \n",
    "            return res_left or res_right\n",
    "\n",
    "        return reach(arr, start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        N =len(arr)\n",
    "        Q = deque([(start)])\n",
    "        seen = set([(start)])\n",
    "        while Q:\n",
    "            idx = Q.popleft()\n",
    "            if arr[idx] == 0:\n",
    "                return True\n",
    "            for nei in [idx + arr[idx], idx-arr[idx]]:\n",
    "                if 0<=nei<N and nei not in seen:\n",
    "                    seen.add(nei)\n",
    "                    Q.append(nei)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        q = deque([start])\n",
    "        vis = [False] * len(arr)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            vis[cur] = True\n",
    "            if arr[cur] == 0: return True\n",
    "            if cur - arr[cur] >= 0 and not vis[cur - arr[cur]]: \n",
    "                vis[cur - arr[cur]] = True\n",
    "                q.append(cur - arr[cur])\n",
    "            if cur + arr[cur] < len(arr) and not vis[cur + arr[cur]]:\n",
    "                vis[cur + arr[cur]] = True \n",
    "                q.append(cur + arr[cur])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        from queue import LifoQueue\n",
    "\n",
    "        length = len(arr)\n",
    "        stack = LifoQueue()\n",
    "        stack.put(start)\n",
    "        arrived = [False for _ in range(length)]\n",
    "        while not stack.empty():\n",
    "            idx = stack.get()\n",
    "            if arr[idx] == 0:\n",
    "                return True\n",
    "            if arrived[idx]:\n",
    "                return False\n",
    "\n",
    "            left, right = idx - arr[idx], idx + arr[idx]\n",
    "            if left >= 0 and not arrived[left]:\n",
    "                stack.put(left)\n",
    "            if right < length and not arrived[right]:\n",
    "                stack.put(right)\n",
    "            arrived[idx] = True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start] == 0: return True\n",
    "        if 0 not in arr: return False\n",
    "        n = len(arr)\n",
    "\n",
    "        q = deque([start])\n",
    "        vis = [False] * n\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            x = arr[i]\n",
    "            vis[i] = True\n",
    "            if x == 0: return True\n",
    "            if i-x >= 0 and not vis[i-x]: q.append(i-x)\n",
    "            if i+x < n and not vis[i+x]: q.append(i+x)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        if arr[start] == 0:\n",
    "            return True\n",
    "        used = {start}\n",
    "        q = collections.deque([start])\n",
    "        while len(q) > 0:\n",
    "            u = q.popleft()\n",
    "            for v in [u + arr[u], u - arr[u]]:\n",
    "                if 0 <= v < n and v not in used:\n",
    "                    if arr[v] == 0:\n",
    "                        return True\n",
    "                    q.append(v)\n",
    "                    used.add(v)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        from collections import deque\n",
    "        n=len(arr)\n",
    "        quene=deque()\n",
    "        quene.append(start)\n",
    "        check=set(range(n))\n",
    "        check.remove(start)\n",
    "        while quene:\n",
    "            cur=quene.popleft()\n",
    "            if arr[cur]==0:\n",
    "                return True\n",
    "            a,b=cur+arr[cur],cur-arr[cur]\n",
    "            if 0<=a<n and a in check:\n",
    "                check.remove(a)\n",
    "                quene.append(a)\n",
    "            if 0<=b<n and b in check:\n",
    "                check.remove(b)\n",
    "                quene.append(b)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start]==0:\n",
    "            return True\n",
    "        n=len(arr)\n",
    "        visited=[[False]*2 for _ in range(n)]   #visited[i][0]:从左向右移动到达下标i,visited[i][1]:从右向左移动到达下标i\n",
    "        q=deque([(start+arr[start],0),(start-arr[start],1)])\n",
    "        while q:\n",
    "            pos,dir=q.popleft()\n",
    "            if pos<0 or pos>=n or visited[pos][dir]:\n",
    "                continue\n",
    "            if arr[pos]==0:\n",
    "                return True\n",
    "            visited[pos][dir]=True\n",
    "            q.append((pos+arr[pos],0))\n",
    "            q.append((pos-arr[pos],1))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start] == 0:\n",
    "            return True\n",
    "        arr_status = {index: False for index in range(len(arr))}\n",
    "        q = queue.Queue()\n",
    "        q.put(start)\n",
    "        arr_status[start] = True\n",
    "        while q.qsize():\n",
    "            for _ in range(q.qsize()):\n",
    "                for index in self.reach(arr, q.get()):\n",
    "                    if arr[index] == 0:\n",
    "                        return True\n",
    "                    if not arr_status[index]:\n",
    "                        q.put(index)\n",
    "                        arr_status[index] = True\n",
    "            # print(arr_status)\n",
    "        return False\n",
    "\n",
    "    def reach(self, arr: List[int], start: int):\n",
    "        ret = []\n",
    "        left = start - arr[start]\n",
    "        right = start + arr[start]\n",
    "        if left >= 0:\n",
    "            ret.append(left)\n",
    "        if right <= len(arr) - 1:\n",
    "            ret.append(right)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        next = [[] for _ in arr]\n",
    "        for i, n in enumerate(arr):\n",
    "            if 0 <= i-n:\n",
    "                next[i].append(i-n)\n",
    "            if i+n < len(arr):\n",
    "                next[i].append(i+n)\n",
    "        nodes = collections.deque()\n",
    "        nodes.append(start)\n",
    "        visited = [False for p in arr]\n",
    "        while nodes:\n",
    "            cn = nodes.popleft()\n",
    "            if arr[cn] == 0:\n",
    "                return True\n",
    "            visited[cn] = True\n",
    "            for nn in next[cn]:\n",
    "                if not visited[nn]:\n",
    "                    nodes.append(nn)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        routes = [[] for i in range(len(arr))]\n",
    "        for i in range(len(arr)):\n",
    "            l = i - arr[i]\n",
    "            if l >= 0:\n",
    "                routes[i].append(l)\n",
    "            r = i + arr[i]\n",
    "            if r < len(arr):\n",
    "                routes[i].append(r)\n",
    "        bfs = collections.deque([start])\n",
    "        visit = [False for i in range(len(arr))]\n",
    "        visit[start] = True\n",
    "        while len(bfs)>0:\n",
    "            i = bfs.popleft()\n",
    "            for j in routes[i]:\n",
    "                if arr[j]==0:\n",
    "                    return True\n",
    "                if not visit[j]:\n",
    "                    visit[j] = True\n",
    "                    bfs.append(j)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        nodedict = {i:[] for i in range(n)}\n",
    "        \n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            if i - arr[i] >= 0:\n",
    "                nodedict[i].append(i - arr[i])\n",
    "            if i + arr[i] < n:\n",
    "                nodedict[i].append(i + arr[i])\n",
    "            if arr[i] == 0:\n",
    "                res.add(i)\n",
    "                \n",
    "        queue = [start]\n",
    "        visited = {start}\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                cur = queue.pop(0)\n",
    "                for j in nodedict[cur]:\n",
    "                    if j in visited:\n",
    "                        continue\n",
    "                    queue.append(j)\n",
    "                    visited.add(j)\n",
    "                    \n",
    "                if cur in res:\n",
    "                    return True\n",
    "           \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "\n",
    "        n = len(arr)\n",
    "        if n==1:\n",
    "            return True\n",
    "\n",
    "        adj_list=[]\n",
    "        for i in range(n):\n",
    "            adj=[]\n",
    "            if i+arr[i]>=0 and i+arr[i]<n:\n",
    "                adj.append(i+arr[i])\n",
    "            if i-arr[i]>=0 and i-arr[i]<n:\n",
    "                adj.append(i-arr[i]) \n",
    "            adj_list.append(adj)\n",
    "\n",
    "        visited=set()\n",
    "        queue=[]\n",
    "        queue.append(start)\n",
    "        visited.add(start)\n",
    "\n",
    "        while queue:\n",
    "            cnt = len(queue)\n",
    "            for _ in range(cnt):\n",
    "                i= queue.pop(0)\n",
    "                for ner in adj_list[i]:\n",
    "                    if arr[ner]==0:\n",
    "                        return True\n",
    "                    if ner not in visited:\n",
    "                        queue.append(ner)\n",
    "                        visited.add(ner)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start] == 0:\n",
    "            return True\n",
    "        n = len(arr)\n",
    "        visited = {(start, 1), (start, -1)}\n",
    "        q = [(start, 1), (start, -1)]\n",
    "        while q:\n",
    "            val, direct = q.pop(0)\n",
    "            if arr[val] == 0:\n",
    "                return True\n",
    "            if direct < 0:\n",
    "                diff = val - arr[val]\n",
    "                if diff >= 0:\n",
    "                    if (diff, 1) not in visited:\n",
    "                        q.append((diff, 1))\n",
    "                        visited.add((diff, 1))\n",
    "                    if (diff, -1) not in visited:\n",
    "                        q.append((diff, -1))\n",
    "                        visited.add((diff, -1))\n",
    "            else:\n",
    "                sums = val + arr[val]\n",
    "                if sums < n:\n",
    "                    if (sums, 1) not in visited:\n",
    "                        q.append((sums, 1))\n",
    "                        visited.add((sums, 1))\n",
    "                    if (sums, -1) not in visited:\n",
    "                        q.append((sums, -1))\n",
    "                        visited.add((sums, -1))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "\n",
    "\n",
    "        n = len(arr)\n",
    "        visited = [0]*n \n",
    "        graph = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i-arr[i]>=0:\n",
    "                graph[i-arr[i]].append(i)\n",
    "            if i+arr[i]<n:\n",
    "                graph[i+arr[i]].append(i)\n",
    "        \n",
    "        bfs = [i for i in range(n) if arr[i]==0]\n",
    "        for i in bfs:\n",
    "            visited[i] = 1 \n",
    "        \n",
    "        while bfs:\n",
    "            tmp_bfs = []\n",
    "            for i in bfs:\n",
    "                for j in graph[i]:\n",
    "                    if j==start:\n",
    "                        return True\n",
    "                    if not visited[j]: \n",
    "                        visited[j] = 1 \n",
    "                        tmp_bfs.append(j)\n",
    "            bfs = tmp_bfs[:]\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i, k in enumerate(arr):\n",
    "            if k == 0:\n",
    "                continue\n",
    "            if i+k < len(arr):\n",
    "                graph[i].append(i+k)\n",
    "            if i-k >= 0:\n",
    "                graph[i].append(i-k)\n",
    "        visited = [False] * len(arr)\n",
    "        q = collections.deque()\n",
    "        q.append(start)\n",
    "        visited[start] = True\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            if arr[i] == 0:\n",
    "                return True\n",
    "            for n in graph[i]:\n",
    "                if not visited[n]:\n",
    "                    q.append(n)\n",
    "                    visited[n] = True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        g = [set() for _ in range(n)]\n",
    "        for i, std in enumerate(arr):\n",
    "            if std == 0:\n",
    "                continue\n",
    "            if i + std < n:\n",
    "                g[i].add(i + std)\n",
    "            if i - std >= 0:\n",
    "                g[i].add(i - std)\n",
    "\n",
    "        visited = [False] * n\n",
    "\n",
    "        q = deque([start])\n",
    "        while len(q) > 0:\n",
    "            v = q.popleft()\n",
    "            if visited[v] != True:\n",
    "                visited[v] = True\n",
    "                if arr[v] == 0:\n",
    "                    return True\n",
    "                for w in g[v]:\n",
    "                    q.append(w)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        graph = collections.defaultdict(list)\n",
    "        destinations = set()\n",
    "        for index, step in enumerate(arr):\n",
    "            if step == 0:\n",
    "                destinations.add(index)\n",
    "                continue\n",
    "\n",
    "            if index+step < len(arr):\n",
    "                graph[index].append(index+step)\n",
    "            if index-step >= 0:\n",
    "                graph[index].append(index-step)\n",
    "            \n",
    "        q = deque([start])\n",
    "        visited = set([start])\n",
    "        while q:\n",
    "            cur_node = q.popleft()\n",
    "            if cur_node in destinations:\n",
    "                return True\n",
    "\n",
    "            for target in graph[cur_node]:\n",
    "                if target not in visited:\n",
    "                    q.append(target)\n",
    "                    visited.add(target)\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        can_reach = {}\n",
    "        check_list = [0] * n\n",
    "        for i, num in enumerate(arr):\n",
    "            if 0 <= i - num < n:\n",
    "                can_reach.setdefault(i - num, set()).add(i)\n",
    "            if 0 <= i + num < n:\n",
    "                can_reach.setdefault(i + num, set()).add(i)\n",
    "        current_set = set()\n",
    "        for i, num in enumerate(arr):\n",
    "            if num == 0 and i in can_reach:\n",
    "                check_list[i] = 1\n",
    "                current_set = current_set.union(can_reach[i])\n",
    "        for i in current_set:\n",
    "            check_list[i] = 1\n",
    "        while current_set:\n",
    "            if start in current_set:\n",
    "                return True\n",
    "            temp_set = set()\n",
    "            for i in current_set:\n",
    "                if i in can_reach:\n",
    "                    temp_set = temp_set.union(can_reach[i])\n",
    "            _temp_set = set()\n",
    "            for i in temp_set:\n",
    "                if check_list[i] == 0:\n",
    "                    check_list[i] = 1\n",
    "                    _temp_set.add(i)\n",
    "            current_set = _temp_set\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        n = len(arr)\n",
    "        tars = []\n",
    "        for i in range(n):\n",
    "            if arr[i] == 0:\n",
    "                tars.append(i)\n",
    "            if 0 <= i+arr[i] < n:\n",
    "                g[i].add(i+arr[i])\n",
    "            if 0 <= i-arr[i] < n:\n",
    "                g[i].add(i-arr[i])\n",
    "        #g表示图\n",
    "        q = deque([start])\n",
    "        vis = [False] * n \n",
    "        vis[start] = True \n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            vis[cur] = True \n",
    "            for x in g[cur]:\n",
    "                if not vis[x]:\n",
    "                    q.append(x)\n",
    "        for t in tars:\n",
    "            if vis[t]:\n",
    "                return True \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if not arr[start]:\n",
    "            return True\n",
    "        n = len(arr)\n",
    "        ins = defaultdict(set)\n",
    "        q = deque()\n",
    "        visited = set()\n",
    "        for i, num in enumerate(arr):\n",
    "            for w in (-1, 1):\n",
    "                nxt = i + w * num\n",
    "                if 0 <= nxt < n:\n",
    "                    ins[nxt].add(i)\n",
    "            if not num:\n",
    "                q.append(i)\n",
    "                visited.add(i)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nxt in ins[cur]:\n",
    "                if nxt == start:\n",
    "                    return True\n",
    "                if nxt not in visited:\n",
    "                    q.append(nxt)\n",
    "                    visited.add(nxt)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        #建图，然后进行遍历BFS或者DFS都可\n",
    "        def buildGraph(arr):\n",
    "            graph = collections.defaultdict(list)\n",
    "            n = len(arr)\n",
    "            for i in range(n):\n",
    "                val = arr[i]\n",
    "                if i-val>=0:\n",
    "                    graph[(i, val)].append((i-val, arr[i-val]))\n",
    "                if i+val<n:\n",
    "                    graph[(i, val)].append((i+val, arr[i+val]))\n",
    "            return graph\n",
    "\n",
    "        def dfs(idx, val):\n",
    "            for (i,v) in graph[(idx, val)]:\n",
    "                if not visited[i] and not flag[0]:\n",
    "                    visited[i] = True\n",
    "                    if v==0:\n",
    "                        flag[0] = True \n",
    "                        return\n",
    "                    else:\n",
    "                        dfs(i,v)\n",
    "        \n",
    "        graph = buildGraph(arr)\n",
    "        visited = [False]*len(arr)\n",
    "        flag = [False]\n",
    "        dfs(start, arr[start])\n",
    "        return flag[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        dct = dict()\n",
    "        for k, v in enumerate(arr):\n",
    "            ka, kb = k - v, k + v\n",
    "            va, vb = None, None\n",
    "            dct[k] = []\n",
    "            if ka in range(len(arr)):\n",
    "                va = arr[ka]\n",
    "                dct[k].append((ka, va))\n",
    "            if kb in range(len(arr)):\n",
    "                vb = arr[kb]\n",
    "                dct[k].append((kb, vb))\n",
    "        if not dct[start]:\n",
    "            return False\n",
    "        klist = [start]\n",
    "        while klist:\n",
    "            new_klist = []\n",
    "            for new_start in klist:\n",
    "                for k, v in dct[new_start]:\n",
    "                    if v == 0:\n",
    "                        return True\n",
    "                    if k in dct:\n",
    "                        new_klist.append(k)\n",
    "                dct.pop(new_start)\n",
    "            klist = new_klist\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        size=len(arr)\n",
    "        edges=defaultdict(list)\n",
    "        for i in range(size):\n",
    "            if i-arr[i]>=0:\n",
    "                edges[i].append(i-arr[i])\n",
    "            if i+arr[i]<size:\n",
    "                edges[i].append(i+arr[i])\n",
    "\n",
    "        visited=[0]*size\n",
    "        flag=False\n",
    "        def dfs(u):\n",
    "            nonlocal flag\n",
    "            visited[u]=1\n",
    "            if arr[u]==0:\n",
    "                flag=True\n",
    "\n",
    "            for v in edges[u]:\n",
    "                if visited[v]==0:\n",
    "                    dfs(v)\n",
    "        dfs(start)\n",
    "        return flag\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        reach_dict = {}\n",
    "        for index, each_num in enumerate(arr):\n",
    "            if each_num != 0:\n",
    "                left_range = index - each_num if index - each_num >= 0 else -1\n",
    "                right_range = index + each_num if index + each_num < len(arr) else -1\n",
    "                reach_dict[index] = (left_range, right_range)\n",
    "        # DFS\n",
    "        visited_index = set()\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int) -> bool:\n",
    "            if arr[index] == 0:\n",
    "                return True\n",
    "            visited_index.add(index)\n",
    "            left_index, right_index = reach_dict[index]\n",
    "            if left_index != -1 and left_index not in visited_index:\n",
    "                if dfs(left_index):\n",
    "                    return True\n",
    "            if right_index != -1 and right_index not in visited_index:\n",
    "                if dfs(right_index):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs(start)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        # 先构建一个下标图\n",
    "        dictarr = defaultdict(set)\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            val = arr[i]\n",
    "            if i-val>=0:\n",
    "                dictarr[i].add((i-val))\n",
    "            if i+val<n:\n",
    "                dictarr[i].add((i+val))                \n",
    "        # print(dictarr)\n",
    "        def dfs(a, marked):\n",
    "            if arr[a] == 0:\n",
    "                return True\n",
    "            for i in dictarr[a]:\n",
    "                if i not in marked:\n",
    "                    marked.append(i)\n",
    "                    if dfs(i, marked): return True\n",
    "    \n",
    "        marked = [start]\n",
    "        if dfs(start, marked):\n",
    "            return True \n",
    "        else: return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        # 先构建一个下标图\n",
    "        dictarr = defaultdict(set)\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            val = arr[i]\n",
    "            if i-val>=0:\n",
    "                dictarr[i].add((i-val))\n",
    "            if i+val<n:\n",
    "                dictarr[i].add((i+val))                \n",
    "        # print(dictarr)\n",
    "        def dfs(a, marked):\n",
    "            if arr[a] == 0:\n",
    "                return True\n",
    "            for i in dictarr[a]:\n",
    "                if i not in marked:\n",
    "                    if dfs(i, marked+[i]): return True\n",
    "           \n",
    "        marked = [start]\n",
    "        if dfs(start, marked):\n",
    "            return True \n",
    "        else: return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        self.vis = [0] * len(arr)\n",
    "        self.ans = False\n",
    "        self.arr = arr\n",
    "        self.dfs(start)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, cur):\n",
    "        if self.ans:\n",
    "            return\n",
    "        if self.vis[cur]:\n",
    "            return\n",
    "        self.vis[cur] = True\n",
    "        if self.arr[cur] == 0:\n",
    "            self.ans = True\n",
    "            return\n",
    "        if cur - self.arr[cur] >= 0:\n",
    "            self.dfs(cur - self.arr[cur])\n",
    "        if cur + self.arr[cur] < len(self.arr):\n",
    "            self.dfs(cur + self.arr[cur])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach1(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start] == 0:\n",
    "            return True\n",
    "        N = len(arr)\n",
    "        visited = set()\n",
    "        queue = [start]\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            for nxt in (cur+arr[cur],cur-arr[cur]):\n",
    "                if 0<=nxt<N and nxt not in visited:\n",
    "                    if arr[nxt] == 0:\n",
    "                        return True\n",
    "                    visited.add(nxt)\n",
    "                    queue.append(nxt)\n",
    "        return False\n",
    "\n",
    "\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        self.res = False\n",
    "        N = len(arr)\n",
    "        self.visited = [False] * N\n",
    "        self.dfs(start,N,arr)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self,curinx,N,arr):\n",
    "        if not self.res and 0<=curinx<N and not self.visited[curinx]:\n",
    "            if arr[curinx] == 0:\n",
    "                self.res = True\n",
    "                return\n",
    "            self.visited[curinx] = True\n",
    "            self.dfs(curinx+arr[curinx],N,arr)\n",
    "            self.dfs(curinx-arr[curinx],N,arr)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        self.res = False\n",
    "        n = len(arr)\n",
    "        self.visit = [0 for i in range(n)]\n",
    "        self.visit[start] = 1\n",
    "        self.bfs(arr,start,n)\n",
    "        return self.res\n",
    "\n",
    "    def bfs(self,arr,start,n):\n",
    "        if arr[start] == 0 or self.res:\n",
    "            self.res = True\n",
    "            return\n",
    "        \n",
    "        next = start+arr[start]\n",
    "        if next<n and self.visit[next]==0:\n",
    "            self.visit[next] = 1\n",
    "            self.bfs(arr,next,n)\n",
    "            self.visit[next] = 0\n",
    "        prev = start-arr[start]\n",
    "        if prev>=0 and self.visit[prev]==0:\n",
    "            self.visit[prev] = 1\n",
    "            self.bfs(arr,prev,n)\n",
    "            self.visit[prev] = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        visited = [False for _ in range(len(arr))]\n",
    "        return self._dfs(start, arr, visited)\n",
    "    \n",
    "    def _dfs(self, i, arr, visited):\n",
    "        if arr[i] == 0:\n",
    "            return True\n",
    "        l, r = i - arr[i], i + arr[i]\n",
    "        if 0 <= l < len(arr) and visited[l] == False:\n",
    "            visited[l] = True\n",
    "            if self._dfs(l, arr, visited):\n",
    "                return True\n",
    "        if 0 <= r < len(arr) and visited[r] == False:\n",
    "            visited[r] = True\n",
    "            if self._dfs(r, arr, visited):\n",
    "                return True\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        tempset = set()\n",
    "        tempset.add(start)\n",
    "\n",
    "        return self.go(n, arr, start, tempset)\n",
    "\n",
    "    def go(self, n, arr, index, tempset):\n",
    "        tempindex = index + arr[index]\n",
    "        if 0<= tempindex <n:\n",
    "            if arr[tempindex] == 0:\n",
    "                return True\n",
    "            if tempindex not in tempset:\n",
    "                tempset.add(tempindex)\n",
    "                if self.go(n, arr, tempindex, tempset):\n",
    "                    return True\n",
    "                tempset.remove(tempindex)\n",
    "        \n",
    "        tempindex = index - arr[index]\n",
    "        if 0<= tempindex <n:\n",
    "            if arr[tempindex] == 0:\n",
    "                return True            \n",
    "            if tempindex not in tempset:\n",
    "                tempset.add(tempindex)\n",
    "                if self.go(n, arr, tempindex, tempset):\n",
    "                    return True\n",
    "                tempset.remove(tempindex)\n",
    "        return False                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr, start):\n",
    "        already_in = set()\n",
    "\n",
    "        return self.dfs(arr, start, already_in)\n",
    "\n",
    "    def dfs(self, arr, index, already_in):\n",
    "        if index in already_in:\n",
    "            return False\n",
    "        if arr[index] == 0:\n",
    "            return True\n",
    "        already_in.add(index)\n",
    "        index_right = index + arr[index]\n",
    "        index_left = index - arr[index]\n",
    "        if (index_right >= 0) and (index_right < len(arr)) and self.dfs(arr, index_right, already_in):\n",
    "            return True\n",
    "        if (index_left >= 0) and (index_left < len(arr)) and self.dfs(arr, index_left, already_in):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        jump = []\n",
    "\n",
    "\n",
    "        def nfs(i):\n",
    "            if i >= len(arr) or i <0:\n",
    "                return False\n",
    "            if arr[i] == 0:\n",
    "                return True\n",
    "            if i in jump:\n",
    "                return False\n",
    "            jump.append(i)\n",
    "            return nfs(i + arr[i]) or nfs(i - arr[i])\n",
    "\n",
    "\n",
    "\n",
    "        return nfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if 0 <= start < len(arr) and arr[start] >= 0:\n",
    "            if arr[start] == 0:\n",
    "                return True\n",
    "\n",
    "            arr[start] = -arr[start]\n",
    "            print(start,\":\", arr[start])\n",
    "            return self.canReach(arr, start+arr[start]) or self.canReach(arr, start-arr[start])\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        def dfs(i):\n",
    "            if i < 0 or i >= len(arr) or arr[i] == -1:\n",
    "                return False\n",
    "            if arr[i] == 0:\n",
    "                return True\n",
    "            step = arr[i]\n",
    "            arr[i] = -1\n",
    "            return dfs(i + step) or dfs(i - step)\n",
    "\n",
    "        return dfs(start)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        # BFS\n",
    "        if 0 <= start < len(arr) and arr[start] >= 0:\n",
    "            if arr[start] == 0:\n",
    "                return True\n",
    "            jump = arr[start]\n",
    "            arr[start] = -1 # 标记一下已经走过的位置\n",
    "\n",
    "            return self.canReach(arr, start + jump) or self.canReach(arr, start - jump)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        # dfs，vis数组避免重复访问\n",
    "        n = len(arr)\n",
    "\n",
    "        vis = [False]*n\n",
    "        def dfs(i):\n",
    "            if arr[i]==0:\n",
    "                return True\n",
    "            res = False\n",
    "            if i+arr[i]<=n-1 and vis[i+arr[i]]==False:\n",
    "                vis[i+arr[i]] = True\n",
    "                res = res or dfs(i+arr[i])\n",
    "            if i-arr[i]>=0 and vis[i-arr[i]]==False:\n",
    "                vis[i-arr[i]] = True\n",
    "                res = res or dfs(i-arr[i])\n",
    "            return res\n",
    "            \n",
    "        vis[start] = True\n",
    "        return dfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        used = set()\n",
    "        def Recursion(i):\n",
    "            if i <0 or i >= len(arr):\n",
    "                return False\n",
    "            if arr[i] == 0:\n",
    "                return True\n",
    "            if i in used:\n",
    "                return False\n",
    "            used.add(i)\n",
    "            return Recursion(i - arr[i]) or Recursion(i + arr[i])\n",
    "        return Recursion(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        visited = set() \n",
    "        return self.dfsHelper(arr,start,visited) \n",
    "\n",
    "    def dfsHelper(self,arr,cur,visited):\n",
    "        if cur >= len(arr) or cur < 0 or cur in visited:\n",
    "            return False\n",
    "        visited.add(cur)\n",
    "        if arr[cur] == 0:\n",
    "            return True \n",
    "\n",
    "        left = self.dfsHelper(arr,cur-arr[cur],visited)\n",
    "        right = self.dfsHelper(arr,cur+arr[cur],visited)\n",
    "\n",
    "        return left or right\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = False    \n",
    "        self.end = []\n",
    "        self.hashmap = defaultdict(int)\n",
    "\n",
    "    def f(self, li, start, end):\n",
    "        if start == end:\n",
    "            return True\n",
    "        if start >= len(li) or start < 0 or self.hashmap[start] == 1:\n",
    "            return False\n",
    "        self.hashmap[start] += 1\n",
    "        return self.f(li, start + li[start], end) | self.f(li, start - li[start], end) \n",
    "\n",
    "\n",
    "\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        self.end.clear()\n",
    "        self.hashmap.clear()\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == 0:\n",
    "                self.end.append(i)\n",
    "        for j in self.end:\n",
    "            self.res |= self.f(arr, start, j)\n",
    "            self.hashmap.clear()\n",
    "            if self.res:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        s = {}\n",
    "        def ser(index):\n",
    "            if index < 0 or index >= n:\n",
    "                return False\n",
    "            if arr[index] == 0:\n",
    "                return True\n",
    "            if index in s:\n",
    "                return False\n",
    "            s[index] = 0\n",
    "            index1 = index - arr[index]\n",
    "            index2 = index + arr[index]\n",
    "            return ser(index1) or ser(index2)\n",
    "        return ser(start)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, A: List[int], start: int) -> bool:\n",
    "\n",
    "        def dfs(i):\n",
    "            if i < 0 or i > len(A) - 1:\n",
    "                return False\n",
    "            if A[i] == 0:\n",
    "                return True\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            t = A[i]\n",
    "            A[i] = len(A)\n",
    "            res = dfs(i + t) | dfs(i - t)\n",
    "            A[i] = t\n",
    "            \n",
    "            memo[i] = res\n",
    "            return res\n",
    "        \n",
    "        memo = {}\n",
    "        return dfs(start)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
